package com.lw.leetcode.tree.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * tree
 * 2426. 满足不等式的数对数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/8 10:26
 */
public class NumberOfPairs {

    public static void main(String[] args) {
        NumberOfPairs test = new NumberOfPairs();

        // 3
//        int[] nums1 = {3, 2, 5};
//        int[] nums2 = {2, 2, 1};
//        int diff = 1;

        // 0
//        int[] nums1 = {3, -1};
//        int[] nums2 = {-2, 2};
//        int diff = -1;

        //
        int[] nums1 = Utils.getArr(100000, -10000, 10000);
        int[] nums2 = Utils.getArr(100000, -10000, 10000);
        int diff = 0;
        System.out.println(diff);

        long l = test.numberOfPairs(nums1, nums2, diff);
        System.out.println(l);

    }

    private Node root = new Node(-1000000000, 1000000000);

    public long numberOfPairs(int[] nums1, int[] nums2, int diff) {
        int length = nums1.length;
        long sum = 0;
        for (int i = 0; i < length; i++) {
            int s = nums1[i] - nums2[i];
            sum += find(root, s + diff);
            add(root, s);
        }
        return sum;
    }

    private int find(Node node, int value) {
        if (node == null) {
            return 0;
        }
        int st = node.st;
        int end = node.end;
        if (end == value) {
            return node.count;
        }
        int m = (st + end) / 2;
        if (m == end) {
            m--;
        }
        if (value <= m) {
            return find(node.left, value);
        }
        return (node.left == null ? 0 : node.left.count) + find(node.right, value);
    }

    private void add(Node node, int value) {
        node.count++;
        int st = node.st;
        int end = node.end;
        if (st == end) {
            return;
        }
        int m = (st + end) / 2;
        if (m == end) {
            m--;
        }
        if (value <= m) {
            Node left = node.left;
            if (left == null) {
                left = new Node(st, m);
                node.left = left;
            }
            add(left, value);
        } else {
            Node right = node.right;
            if (right == null) {
                right = new Node(m + 1, end);
                node.right = right;
            }
            add(right, value);
        }
    }

    private static class Node {
        private int st;
        private int end;
        private int count;
        private Node left;
        private Node right;

        public Node(int st, int end) {
            this.st = st;
            this.end = end;
        }
    }

}
